Day 25 - 演算法入門理解 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2021 iThome 鐵人賽

DAY 25

Modern Web

Javascript 從寫對到寫好系列第 25 篇

Day 25 - 演算法入門理解

13th鐵人賽 algorithm big o

ycchiuuuu

團隊鐵人賽臻融一

2021-10-10 19:57:04

1505 瀏覽

分享至

前言

如果昨天是資料結構，那今天必然是來討論演算法啦！

「演算法」是另一個會讓許多非本科系的 developer 嚇到的詞彙，會覺得好像是很高深難懂的技術，應該都是 Google 等級的程式設計師才會用到吧？

但很神奇的是，明明是看起來這麼難的一個詞彙，反而滿常出現在媒體用語中的：

所以今天讓我們來揭開演算法神秘的面紗吧！

跟昨天一樣，今天主軸在於讓大家初步認識演算法，沒有要帶著大家到處去刷題，如果有興趣想用演算法來實際解題，歡迎到我的隊友系列文，用 LeetCode 刷題來練習！

演算法是什麼？

由有限步驟所構成的集合，可以用於解決某一個特定的問題。

簡單來說，有點像是「解決某個問題的步驟流程」，比如在生活上，我們要做家事洗衣服：

把衣服放進洗衣袋
把洗衣袋及其他衣服都丟進洗衣機
放入洗衣精
打開洗衣機電源
選擇洗衣模式，按下啟動
完成

沒錯，上述五個步驟就是為了完成「洗衣服」這個任務，的其中一種演算法！那有沒有其它演算法？

有啊！衣服一定要自己洗嗎？

image alt

把衣服交給媽媽
完成

所以，要完成一件事情，演算法不只一種唷！

這只是個範例，衣服請自己洗嘿！

其實，「如何把大象放進冰箱裡」這個冷笑話，也是演算法的一種哦：

把冰箱門打開
把大象放進去
把冰箱門關上

是不是步驟非常明確，而且能夠解決問題呢XD

而在計算機科學的領域，演算法其實也是在做同樣的事情，我們透過設計一連串的指令、動作，讓電腦去執行，以便協助我們解決一些特定問題。

因此，就算是最簡單的：我想條列出商品名稱與對應的價錢，都是演算法的一種哦！

const products = [
    { name: 'TV', price: 12000 },
    { name: 'laptop', price: 25000 },
    { name: 'washing machine', price: 8000 },
];

products.forEach(product => console.log(`${product.name} 的價錢是 ${product.price}`));

執行結果

TV 的價錢是 12000
laptop 的價錢是 25000
washing machine 的價錢是 8000

演算法有好壞之分嗎？

演算法其實就是「解決問題的方法」，所以這個問題應該改成：

解決問題的方法有好壞之分嗎？

嗯。。。聽起來是有的，只是我們不會說哪個方法絕對好，而是會用兩個指標來衡量：動用的資源以及花費的時間。

而這兩個指標放在計算機科學領域，就是你曾經聽過的：

動用的資源：空間複雜度
花費的時間：時間複雜度

空間複雜度（Space Complexity）

空間複雜度就是，我用了多少記憶體空間來完成這件事。

比如要把一個陣列的順序完全反轉：

const reverseArr = (input) => {
    const output = [];
    input.forEach(item => output.unshift(item));
    console.log(output);
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

執行結果

[5, 4, 3, 2, 1]

可以看到為了達成「反轉」這件事情，我多宣告了一個 output 陣列(花到額外的空間來放)，裡面總共有五格，所以看起來 reverseArr 的空間複雜度是 5？

感覺怪怪的對吧！因為這個 output 會根據 input 進來的參數大小，而有所不同，因此我們不能夠直接說空間複雜度是 5。

Big O notation（Big O 表示法）

我們使用 Big O notation，表達在「最壞情況下的複雜度等級」，如果像上例複雜度會隨著 input 線性變動的，會用 O(n) 來表示。

那如果不會隨著 input 變動的會像這樣：

const reverseArr = (input) => {
    let temp;
    const length = input.length;
    for(let i = 0; i<=length/2; i++) {
        temp = input[i];
        input[i] = input[length-i-1];
        input[length-i-1] = temp;
    }
    console.log(input);
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

執行結果

[5, 4, 3, 2, 1]

可以看到上面的寫法，同樣是為了達成「反轉」這件事情，但我都在 input 本體上面操作，完全沒有使用到額外的空間 output，也就是說，無論 input 的 length 有多大，這個函式都不會花費更多空間，稱之為 O(1)。

其中 1 其實是代表常數，並不是真的只花 1 個空間，而是表達不會隨著 input.length 變動

上面還有提到另一個重點是，Big O 代表的是「最壞情況」，會這樣說是因為執行一段程式所花費的時間或空間，有可能有三種情況：

最佳情況
平均情況
最壞情況

比如說，我們要從陣列中找到一個元素，只要找到就可以不用繼續找了：

const findElement = (input, element) => {
    const length = input.length;
    for(let i = 0; i<length; i++) {
        if (input[i] === element) break;
    }
};

const arr = [1, 2, 3, 4, 5];
findElement(arr, 3);

像上面這種程式，執行 findElement(arr, 3) 只要跑三次迴圈就結束了，但如果執行 findElement(arr, 5) 就要跑五次迴圈(雖然這個範例的空間複雜度都是一樣的)。

因此我們會有上述三種情況，但計算機科學領域特別重視「上限」，才能夠確保系統能夠負荷最嚴重的狀況，所以我們才會只強調「最壞狀況」。

時間複雜度（Time complexity）

時間複雜度則是，我花了多少時間來完成這件事。

但這邊有一點要特別注意，並不是單純指花了幾分鐘來執行，因為每台電腦效能不一樣，我們不是要衡量哪一台電腦比較快，而是「不同的程式寫法在同一台電腦上執行」時的複雜度，因此我們會使用「執行了多少指令」來計算複雜度。

以剛剛上面的例子：

const reverseArr = (input) => {
    const output = []; // 1
    input.forEach(item => output.unshift(item)); // n
    console.log(output); // 1
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

可以看到我在註解的地方寫上了複雜度等級，總共合起來是 n+2，我們只取次方最高的 n，因為當 input 增加時，變化最大的會是最高次方的 n，所以 reverseArr 的時間複雜度就是 O(n)。